package com.cuz.hot100;

import java.util.Arrays;

public class Q16ThreeNumSumClosest {
    public static void main(String[] args) {


        class A{
            public int threeSumClosest(int[] nums, int target) {
                Arrays.sort(nums);
                int result = nums[0]+nums[1]+nums[2];

                if(result>=target) {
                    return result;
                }
                int abs = Math.abs(target-result);
                for(int i = 0; i<nums.length; i++){
                    int left = i+1;
                    int right = nums.length-1;
                    while(left<right){
                        int temp = nums[left]+nums[i]+nums[right];
                        int tempAbs =  Math.abs(target-temp);
                        if(target == temp){
                            return temp;
                        }
                        if(tempAbs < abs){
                            result = temp;
                            abs = tempAbs;
                        }
                        if(temp>target){
                            right--;
                        }else{
                            left++;
                        }

                    }
                }

                return result;
            }
        }
        //[1,1,-1,-1,3]
        //-1
        int[] ints = {-1000,-5,-5,-5,-5,-5,-5,-1,-1,-1};
        System.out.println(new A().threeSumClosest(ints,-14));
        System.out.println(threeSumClosest1(ints, -1));
    }

    public static int threeSumClosest1(int[] nums, int target) {
        Arrays.sort(nums);
        int res = Integer.MAX_VALUE;
        int abs = Integer.MAX_VALUE;
        for (int start = 0; start < nums.length - 2; start++) {
            int mid = start + 1;
            int end = nums.length - 1;
            while (mid < end) {
                int tempSum = nums[start] + nums[mid] + nums[end];
                int tempAbs = Math.abs(target - tempSum);
                if (tempAbs < abs) {
                    abs = tempAbs;
                    res = tempSum;
                }
                if (tempSum == target) {
                    return tempSum;
                }else if (tempSum>target){
                    end--;
                }else {
                    mid++;
                }
            }
        }
        return res;
    }
}
